#ifndef __HEAP_H__
#define __HEAP_H__

#include "vector.h"

/* Make heap from range
 * Rearranges the elements in the range [first,last) in such a way that they form a heap.
 * A heap is a way to organize the elements of a range that allows for fast retrieval of the element
 * with the highest value at any moment (with pop_heap), even repeatedly, while allowing for fast
 * insertion of new elements (with push_heap). The element with the highest value is always pointed
 * by first. The order of the other elements depends on the particular implementation, but it is
 * consistent throughout all heap-related functions of this header. The elements are compared using
 * cmp.
 */
void Make_Heap(Vector *v, size_t first, size_t last, int (*cmp)(void *, void *));

/* Push element into heap range
 * Given a heap in the range [first,last-1), this function extends the range considered a heap to
 * [first,last) by placing the value in (last-1) into its corresponding location within it. A range
 * can be organized into a heap by calling make_heap. After that, its heap properties are preserved
 * if elements are added and removed from it using push_heap and pop_heap, respectively.
 */
void Heap_Push(Vector *v, size_t first, size_t last, int (*cmp)(void *, void *));

/* Pop element from heap range
 * Rearranges the elements in the heap range [first,last) in such a way that the part considered a
 * heap is shortened by one: The element with the highest value is moved to (last-1). While the
 * element with the highest value is moved from first to (last-1) (which now is out of the heap),
 * the other elements are reorganized in such a way that the range [first,last-1) preserves the
 * properties of a heap. A range can be organized into a heap by calling make_heap. After that, its
 * heap properties are preserved if elements are added and removed from it using push_heap and
 * pop_heap, respectively.
 */
void Heap_Pop(Vector *v, size_t first, size_t last, int (*cmp)(void *, void *));

#endif //__HEAP_H__
